# 希尔排序
# 书上给的方法

from utils.array_utils import sjlb, check


def shell(array):
    '''
    希尔排序
        1.选择一个增量序列t1,t2,...,tk,其中ti>tj,tk=1
        2.按增量序列个数K，对序列进行K躺排序
        3.每趟排序，根据对应的增量ti，将待排序分割成若干长度为m的子序列，分别对给子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，
        表长度即为整个序列的长度
    '''
    half = len(array) // 2
    # 第一层循环 指定步长
    while half > 0:
        i = 0
        # 第二层循环 根据步长分组
        # while i < len(array):
        for i in range(half, len(array)):
            # print(array[i], end=' ')
            while i >= half and array[i] < array[i - 1]:
                array[i], array[i - half] = array[i - half], array[i]
                i -= half
        half //= 2

    # print(arr)
    # print(temp)


if __name__ == '__main__':
    # l = [40, 82, 17, 35, 52, 73, 54, 9, 1]
    # shell(l)
    # print(l)

    for i in range(1000):
        l = sjlb()
        # print(l)
        shell(l)
        if not check(l):
            print('wrong: ', l)
